#include <bits/stdc++.h>
using namespace std;
// singal linked list node def:
typedef struct node
{
    int data;
    struct node *next;
} node, *slist;
/**
 * @brief 按位序查找函数,位序从1开始
 * @param &L which list do you want to find?
 * @param i to find which node in this list?
 * @return p pointer.
 */
slist find_with_index(slist &L, int i)
{
    node *p = L;
    int j = 0;
    while (p != NULL && j < i)
    { // find i node!
        p = p->next;
        j++;
    }
    return p;
}
/**
 * @brief find with value
 * @param e the value you want find.
 * @param i the index return.
 */
slist find_with_value(slist &L,int e,int &i){
    node *p=L;
    i=0;
    while(p!=NULL){
        p=p->next;
        i++;
        if(p->data==e){
            return p;
        }
    }
    return NULL;
}

/**
 * @brief 正向建立单链表
 * @return 返回头节点L的指针
 */
slist forwardCreat(slist &L)
{
    L = (node *)malloc(sizeof(node));
    L->next = NULL;
    node *s, *r = L; // r是一个尾指针
    int x;
    cin >> x;
    while (x != 9999)
    {
        s = (node *)malloc(sizeof(node));
        s->data = x;//为当前的节点赋值数据
        r->next = s;//将尾指针更新到新的s
        r = s;//移动尾指针
        cin >> x;
    }
    r->next = NULL;
    return L;
}
/**
 * @brief print list
 * @param &L which list do you want to print?
 *
 */
void printlist(slist L)
{
    node *p = L->next;
    int i = 1;
    while (p != NULL)
    {
        cout << "node " << i << " is:" << p->data << endl;
        p = p->next;
        i++;
    }
}
/**
 * @brief add a data in rank i
 * @param L which list do you want add?
 * @param i which rank?
 * @param e the value of the data.
 */
slist addWithRank(slist &L, int i, int e)
{
    // if(i==1){
    //     slist s=new node;
    //     s->data=e;
    //     s->next=L;

    // }
    slist p = find_with_index(L, i - 1);
    slist s = (node *)malloc(sizeof(node));
    s->next = p->next;
    p->next = s;
    s->data = e;
    return L;
}
/**
 * @brief delete data with rank i.
 */
slist delWithRank(slist &L, int i)
{
    node *p = find_with_index(L, i - 1);//找到要删掉的上一个节点p
    //跨过p的下一个节点了
    node *ans=p->next;
    p->next=ans->next;
    delete(ans);
    return L;
    
}
/**
 * @brief 在指定节点之前插入一个数字
 * @param p 接受查询到的节点
 * @param e the value
 */
//slist preInsert(slist &L,node *p,int e){
    
//}
int main()
{
    //SetConsoleOutputCP(65001);
    slist L;
    cout<<"input list value:(input 9999 to stop)\n";
    forwardCreat(L);
    printlist(L);
    cout<<"input what index do you want to found:\n";
    int i;
    cin >> i;
    slist ans = find_with_index(L, i);
    cout << ans->data << endl;
    cout<<"input index do you add:(index value)\n";
    int e;
    cin >> i >> e;
    addWithRank(L, i, e);
    printlist(L);
    cout<<"input index do you delete:\n";
    cin >> i;
    delWithRank(L, i);
    printlist(L);
    cout<<"输入值，按值查找。";
    int x;
    cin>>x;
    i=0;
    node*p=find_with_value(L,x,i);
    if(p!=NULL){
        cout<<"找到值为"<<x<<"的节点 "<<"在"<<"node"<<i<<endl;
    }
    else cout<<"value not found!";

    return 0;
}